﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0153_MajorityElement : IAlgorithm
    {
        // 多数元素

        // 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
        // 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

        // 进阶：
        //  尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 1, 2, 4, 4, 4 };
            // 算法执行与打印
            //Console.WriteLine(MajorityElement());
        }

        // 算法
        public int MajorityElement(int[] nums)
        {
            int target = nums[0];
            int count = 1;
            for (int i = 1; i < nums.Length; i++)
                if (count == 0)
                {
                    target = nums[i];
                    count++;
                }
                else if (nums[i] != target)
                    count--;
                else
                    count++;
            return target;
        }
    }
}
